package Easy;
// 70.爬楼梯
public class Solution70 {
    // 本题思想：动态规划 f(x)=f(x-1)+f(x-2) 因为x-1 != x-2 所以爬到x-1和爬到x-2的方法不然不会重复。
    public int climbStairs(int n) {
        //采用滚动数组的形式，将空间复杂度降低到0(1)
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        int p = 1;
        int q = 2;
        int r = 0;
        for(int i = 2 ; i < n ; i++){
            r=p+q;
            p=q;
            q=r;
        }
        return r;

    }
}
